﻿using System;
using System.Collections.Generic;

namespace AlgorithmPractice;

/// <summary>
/// 递归编程的方法，为给定的整数 n，找到所有可能的分解（1 在解中最多只能出现 1 次）
/// 例如，输入 8，输出是可以是 1x8, 8x1, 2x4, 4x2, 1x2x2x2, 1x2x4, ……
/// </summary>
public class Decomposition
{
    public static void Get(int number, List<int> result)
    {
        if (number == 1)
        {
            Console.WriteLine(string.Join("*", result));
            return;
        }

        for (var i = number; i >= 1; i--)
        {
            if (i == 1 && result.Contains(i))
            {
                continue;
            }

            if (number % i == 0)
            {
                var newResult =
                    System.Text.Json.JsonSerializer.Deserialize<List<int>>(
                        System.Text.Json.JsonSerializer.Serialize(result));
                newResult.Add(i);
                Get(number / i, newResult);
            }
        }
    }
}